import java.util.*;
public class FindXSum {
     // 假设元素的最大值不会超过这个范围
    private static final int MAX_ELEMENT_VALUE = 1000000; // 可根据实际情况调整

    public int[] findXSum(int[] nums, int k, int x) {
        int[] ans = new int[nums.length - k + 1];
        for (int i = 0; i < ans.length; i++) {
            int[] count = new int[1001];
            for (int j = i; j < i + k && j < nums.length; j++) {
                count[nums[j]]++;
            }
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? b[0] - a[0] : b[1] - a[1]);
            for (int j = 0; j < 1001; j++) {
                if (count[j] > 0) {
                    pq.offer(new int[]{j, count[j]});
                }
            }
            int sum = 0;
            int d = 0;
            while (!pq.isEmpty() && d < x) {
                int[] curr = pq.poll();
                sum += curr[0] * curr[1];
                d++;
            }

            ans[i] = sum;
        }
        return ans;
    }

    public long[] findXSum2(int[] nums, int k, int x){
        int n = nums.length;
        long[] ans = new long[n - k + 1];
        
        // 使用数组统计频率，比HashMap更高效
        int[] freq = new int[MAX_ELEMENT_VALUE + 1];
        
        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            freq[nums[i]]++;
        }
        
        // 计算第一个窗口的结果
        ans[0] = (long)calculateXSum(freq, x);
        
        // 滑动窗口，仅更新变化的元素
        for (int i = 1; i <= n - k; i++) {
            // 移除离开窗口的元素
            int outElement = nums[i - 1];
            freq[outElement]--;
            
            // 添加新进入窗口的元素
            int inElement = nums[i + k - 1];
            freq[inElement]++;
            
            // 计算当前窗口的结果
            ans[i] = (long)calculateXSum(freq, x);
        }
        
        return ans;


    }

    private long calculateXSum(int[] freq, int x) {
        // 创建一个列表保存所有非零频率的元素及其频率
        List<int[]> elements = new ArrayList<>();
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] > 0) {
                elements.add(new int[]{i, freq[i]});
            }
        }
        
        // 如果x大于等于元素种类，直接计算所有元素的和
        if (x >= elements.size()) {
            long sum = 0;
            for (int[] elem : elements) {
                sum += (long)elem[0] * elem[1];
            }
            return sum;
        }
        
        // 排序：先按频率降序，相同频率时按元素值降序
        elements.sort((a, b) -> {
            if (a[1] != b[1]) return b[1] - a[1];
            return b[0] - a[0];
        });
        
        // 取前x个元素计算和
        long sum = 0;
        for (int i = 0; i < x; i++) {
            sum += (long)elements.get(i)[0] * elements.get(i)[1];
        }
        
        return sum;
    }
  public static void main(String[] args) {
    int[] nums = {3,8,7,8,7,5};
    int k = 2, x = 2;
    int[] ans = new FindXSum().findXSum(nums, k, x);
    long[] ans2 = new FindXSum().findXSum2(nums, k, x);
    for (int i = 0; i < ans.length; i++) {
      System.out.print(ans[i] + " ");
 
    }
    for (int i = 0; i < ans.length; i++) {

      System.out.print(ans2[i] + " ");
    }

  }
}


// 给你一个由 n 个整数组成的数组 nums，以及两个整数 k 和 x。

// 数组的 x-sum 计算按照以下步骤进行：

// 统计数组中所有元素的出现次数。
// 仅保留出现次数最多的前 x 个元素的每次出现。如果两个元素的出现次数相同，则数值 较大 的元素被认为出现次数更多。
// 计算结果数组的和。
// 注意，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。

// 返回一个长度为 n - k + 1 的整数数组 answer，其中 answer[i] 是 子数组 nums[i..i + k - 1] 的 x-sum。

// 子数组 是数组内的一个连续 非空 的元素序列。

 

// 示例 1：

// 输入：nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

// 输出：[6,10,12]

// 解释：

// 对于子数组 [1, 1, 2, 2, 3, 4]，只保留元素 1 和 2。因此，answer[0] = 1 + 1 + 2 + 2。
// 对于子数组 [1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此，answer[1] = 2 + 2 + 2 + 4。注意 4 被保留是因为其数值大于出现其他出现次数相同的元素（3 和 1）。
// 对于子数组 [2, 2, 3, 4, 2, 3]，只保留元素 2 和 3。因此，answer[2] = 2 + 2 + 2 + 3 + 3。
// 示例 2：

// 输入：nums = [3,8,7,8,7,5], k = 2, x = 2

// 输出：[11,15,15,15,12]

// 解释：

// 由于 k == x，answer[i] 等于子数组 nums[i..i + k - 1] 的总和。